解题思路

其实这就是Hamilton路径的模板题 $\to ​$

根本做法其实是状压DP

用b数组存边，然后f数组用来跑$DP$

用$i$表示 状压后，已经走过的点有哪些（当然啦，包含下面的$j$点），为f数组的第一维

用$j$表示 最后到的是哪个点，为f数组的第二维

然后对于每种情况，可以从其他状态转移过来，这里就不详述了，具体的见代码

Code

#include<bits/stdc++.h>
#define INF 0x7f7f7f7f
#define N 19
using namespace std;
int n,m,Max,res,ans;//Max表示每一位都取的状压值（也就是范围）
int b[N][N],f[1<<19][N];
inline int read() {
    int s=0;
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int main()
{
    int i,j,k,x,y;
    n=read(),m=read();
    for(i=1;i<=m;i++)//单向边
        x=read(),y=read(),b[x][y]=read();
    Max=(1<<n)-1;//求范围，f[1][0]=0
    for(i=2;i<=Max;i++) {//因为必经过0号点，所以直接从状态2开始，虽然2无意义，但是你要赋初值啊
        for(j=0;j<n;j++) {//就是枚举，判断可以 以哪些点为终点
            f[i][j]=-INF;//赋初值
            if((i>>j)&1) {//判断
                res=i^(1<<j);//除去为结尾的这个点，可以从哪些状态转移过来
                for(k=0;k<n;k++)//再枚举
                    if((res>>k)&1&&b[k][j])//再判断，要注意有边才能走
                        f[i][j]=max(f[i][j],f[res][k]+b[k][j]);//求较大值
            }
        }
    }
    --n;
    for(i=1+(1<<n);i<=Max;i++)//以n为结尾的各种情况，i赋的初值是为了保证n-1这个点能取到
        ans=max(ans,f[i][n]);
    printf("%d",ans);
    return 0;
}

一点小问题

可以自行思考一下时间复杂度

这里是不会超的，但是将$n$改为$20$时，仍不会$T$，暴力就是这么优秀

devil.